Преобразование постфиксной записи в префиксную

Цель

Ваша задача — преобразовать постфиксное выражение (обратная польская нотация) в эквивалентное префиксное выражение (польская нотация), построив и обойдя дерево выражений.

Алгоритм

1. Построить дерево выражения: Обработать постфиксное выражение слева направо, используя стек.
   • Когда встречается операнд (например, A, B), создать для него дерево из одного узла и поместить его в стек.
   • Когда встречается оператор (например, +, *) найден, из стека извлекаются два дерева. Первое извлечённое — правый потомок (T₂), а второе — левый потомок (T₁). Создать новое дерево с оператором в качестве корня и поместить его обратно в стек.
2. Сгенерировать префиксную строку: После обработки всех токенов стек будет содержать полное дерево выражения. Выполнить обход в прямом порядке (корень → левое → правое) этого дерева, чтобы получить окончательное префиксное выражение.

Пример

Для постфиксного выражения A B + C *, алгоритм строит следующее дерево:

  *
   / \
  +   C
 / \
A   B

Обход в прямом порядке даёт префиксное выражение: * + A B C.

Формат ввода-вывода

Ввод

• Строка 1: Целое число N (1 ≤ N ≤ 1000), количество токенов.
• Строка 2: Постфиксное выражение, содержащее N токенов, разделённых пробелами.

Правила токенов

• Операнды: Одиночные заглавные буквы (A-Z).
• Операторы: Четыре бинарных оператора: +, -, *, /.

Вывод

• Одна строка, содержащая соответствующее префиксное выражение, где токены разделены пробелами.

Примеры

Пример 1:

5

A B + C *

* + A B C

Пример 2:

7

A B C * + D /

/ + A * B C D

Пример 3:

7

A B + C D - *

* + A B - C D

Ограничения